package com.yun.algorithm.sort;

import java.util.Arrays;

public class ShellSort {
    /*
        分组实现插入，每组元素间隙称为gap
        每轮排序后gap逐渐变小，直到gap为1完成排序
        对插入排序的优化，让元素更快速地交换到最终位置
     */
    public static void sort(int[] a) {
        //a.length/2
        for (int gap = a.length >> 1; gap >= 1; gap = gap >> 1) {
            for (int low = gap; low < a.length; low++) {
                int t = a[low];
                int i = low - gap;
                //自右向左找插入位置
                while (i >= 0 && t < a[i]) {
                    a[i + gap] = a[i];
                    i-=gap;
                }
                //找到插入位置
                if (i != low - gap) {
                    a[i + gap] = t;
                }
            }
        }
    }


}
